---
title: "重新排序"
created: 2025-11-28
tags:
  - 算法
---

# 重新排序

## 题目 [重新排序](https://www.acwing.com/problem/content/4658/)

![[image-504dc68f.png]]

## 思路分析

![[image-b53e5a99.png]]

## 代码实现

```typescript
#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N=1e5+10;

LL a[N],s[N];

LL b[N];

priority_queue<int> pq;

int n,m;

int main()

{

    cin>>n;

    for(int i=1;i<=n;i++){

        cin>>a[i];

        pq.push(a[i]);

        s[i]=s[i-1]+a[i];

    }

    cin>>m;

    LL oldres=0;

    while(m--){

        int l,r;

        cin>>l>>r;

        oldres+=s[r]-s[l-1];

        b[l]++;

        b[r+1]--;

    }

    for(int i=1;i<=n;i++){

        b[i]+=b[i-1];

    }

    //b中其实存放的是每个位置上的数将要被算到的次数

    //把它排个序 再把值最大的数用最多的次数算 就是最大答案

    sort(b+1,b+n+1,greater<int>());

    LL newres=0;

    for(int i=1;i<=n;i++){

        int val=pq.top();

        pq.pop();

        newres+=val*b[i];

    }

    cout<<newres-oldres;

    return 0;

}
```

```cpp
#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N=1e5+10;

LL a[N],s[N];

LL b[N];

int n,m;

int main()

{

    cin>>n;

    for(int i=1;i<=n;i++){

        cin>>a[i];

        s[i]=s[i-1]+a[i];

    }

    cin>>m;

    LL oldres=0;

    while(m--){

        int l,r;

        cin>>l>>r;

        oldres+=s[r]-s[l-1];

        b[l]++;

        b[r+1]--;

    }

    for(int i=1;i<=n;i++){

        b[i]+=b[i-1];

    }

    sort(b+1,b+n+1);

    sort(a+1,a+n+1);

    LL newres=0;

    for(int i=1;i<=n;i++){

        newres+=a[i]*b[i];

    }

    cout<<newres-oldres;

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[耍杂技的牛|耍杂技的牛]] 🏠 [[00-刷题理模型]] ➡️ [[2-Learning/02-算法/03-刷题理模型/贪心相关模型/排序 权贪心（短作业优先 重权值优先）/鱼塘钓鱼|鱼塘钓鱼]]